#leetcode题目62：不同路径
#难度：中等
#时间复杂度：O(m*n)
#空间复杂度：O(m*n)
#方法：动态规划

from typing import List
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp=[[0]*n for _ in range(m)]
        dp[0][0]=1
        for i in range(m):
            dp[i][0]=1
        for j in range(n):
            dp[0][j]=1
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
        return dp[-1][-1]

#测试数据
m=3
n=7
#预期输出：28
solution=Solution()
print(solution.uniquePaths(m,n))

m=3
n=2
#预期输出：3
solution=Solution()
print(solution.uniquePaths(m,n))



